Efficient Maximum-Likelihood Decoding of Linear Block Codes on Binary Memoryless Channels

摘要

In this work, we consider efficient maximum-likelihood decoding of linearblock codes for small-to-moderate block lengths. The presented approach is abranch-and-bound algorithm using the cutting-plane approach of Zhang and Siegel(IEEE Trans. Inf. Theory, 2012) for obtaining lower bounds. We have comparedour proposed algorithm to the state-of-the-art commercial integer programsolver CPLEX, and for all considered codes our approach is faster for both lowand high signal-to-noise ratios. For instance, for the benchmark (155,64)Tanner code our algorithm is more than 11 times as fast as CPLEX for an SNR of1.0 dB on the additive white Gaussian noise channel. By a small modification,our algorithm can be used to calculate the minimum distance, which we haveagain verified to be much faster than using the CPLEX solver.